package com.samxcode.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Given a string containing just the characters '(' and ')', find the length of the longest valid
 * (well-formed) parentheses substring.
 * 
 * For "(()", the longest valid parentheses substring is "()", which has length = 2.
 * 
 * Another example is ")()())", where the longest valid parentheses substring is "()()", which has
 * length = 4.
 * 
 * @author Sam
 *
 */
public class LongestValidParentheses {

    public int longestValidParentheses(String s) {
        int max = 0;
        //the position of last invalid ")"
        int last = -1;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.addFirst(i);
            } else {
                if (stack.isEmpty()) {
                    // record the position before first left parenthesis
                    last = i;
                }
                stack.pollFirst();
                // if stack is empty mean the position before the valid left parenthesis is "last"
                if (stack.isEmpty()) {
                    max = Math.max(max, i - last);
                } else {
                    max = Math.max(max, i - stack.peekFirst());
                }
            }
        }
        return max;
    }
}
